编译原理之证明LL(1)文法

一个文法G是LL(1)的，当且仅当G的任意两个不同的产生式A -> α | β 满足下面的条件： 1. 不存在终结符号a使得α 和 β 都能够推导出以a开头的串。 2. α 和 β中最多只有一个可以推导出空串。 3. 如果 β =>* ε，那么α不能推导出任何以FOLLOW(A)中某个终结符号开头的串。类似的，如果 α =>* ε，那么β不能推导出任何以FOLLOW(A)中某个终结符号开头的串。

前面两个条件等价说FIRST(α) 和FIRST(β)是不相交的集合。第三个条件等价于说如果ε在FIRST(β)中，那么FIRST(α)和FOLLOW(A)是不相交的集合，并且当ε在FIRST(α)中时类似结论成立。

文法G[E]: 1. E -> TE’ 2. E’-> +E| ε 3. T -> FT’ 4. T’-> T| ε 5. F -> PF’ 6. F’ -> *F’| ε 7. P -> (E) | a | b | ∩ 证明该文法是LL(1)文法

(1) FIRST集合(这里只求非终结符号的FIRST集合)

FIRST(E) = { ( , a , b , ∩ } FIRST(T) = { ( , a , b , ∩ } FIRST(F) = { ( , a , b , ∩ }; FIRST(P) = { ( , a , b , ∩ }; FIRST(E’) = { + , ε }; FIRST(T’) = { ( , a , b , ∩ , ε }; FIRST(F’) = { * , ε };

(2) FOLLOW集合

FOLLOW(E) = FOLLOW(E’) + { ) ，$} FOLLOW(E’) = FOLLOW(E) = { ) ，\$ } FOLLOW(T) = FIRST(E’) / ε +FOLLOW(T’) = { + , ) , \$ } FOLLOW(T’) = FOLLOW(T) = { + , ) , \$ } FOLLOW(F) = FIRST(T’) / ε +FOLLOW(T) = { ( , a , b , ∩ , + , ) ,\$ } FOLLOW(F’) = FOLLOW(F) = { ( , a , b , ∩ , + , ) ,\$ } FOLLOW(P) = FIRST(F’) / ε + FOLLOW(F) = {* , ( , a , b , ∩ , + , ), \$ }

注：关于FIRST集合和FOLLOW集合的计算，请参照这篇博客 编译原理之计算FIRST集合和FOLLOW集合

(3) 证明是LL(1)文法 对于E’-> +E’| ε ，( FIRST(+E’) = { + } ) ∩ ( FIRST( ε ) = { ε } )= ∅ 对于T’-> T| ε ，( FIRST(T) = { ( , a , b , ∩ } ) ∩ ( FIRST( ε ) = { ε } )= ∅ 对于F’ -> *F’| ε ，( FIRST(*F’) = { * } ) ∩ ( FIRST( ε ) = { ε } )= ∅ 对于P -> (E) | a | b | ∩ ，( FIRST( (E) ) = { ( } ) ∩ ( FIRST( a ) = { a } ) ∩ ( FIRST( b ) = { b } ) ∩ ( FIRST( ∩ ) = { ∩ } )= ∅

对于E’-> +E| ε , (FIRST(+E) = { + }) ∩ (FOLLOW(E’) = { ) ，$ }) = ∅ 对于T’-> T| ε , (FIRST(T) =( , a , b , ∩) ∩ (FOLLOW(T’) = {+ , ) , $ }) = ∅ 对于F’ -> *F’| ε , (FIRST(*F’) = { * }) ∩ (FOLLOW(F’) = { ( , a , b , ∩ , + , ) ,$ }) = ∅

得证，该文法是LL(1)文法。

下面哪些文法是LL(1)的，并说明理由 (1) 文法： 1. S -> Abc 2. A -> a | ε 3. B -> b | ε

(2) 文法： 1. S -> ABBA 2. A -> a | ε 3. B -> b | ε

(1)该文法不含有左递归 FIRST集合

FIRST(S) = {a , b , ε } FIRST(A) = {a , ε } FIRST(B) = {b , ε }

FOLLOW集合

FOLLOW(S) = { $ } FOLLOW(A) = {b} FOLLOW(B) = { }

对于A -> a | ε ，FIRST(a) ∩ FIRST( ε ) = ∅ 对于B -> b | ε ，FIRST(b) ∩ FIRST( ε ) = ∅ FIRST(a) ∩ FOLLOW(A) = ∅ FIRST(b) ∩ FOLLOW(B) = ∅

符合LL(1)文法的要求，是LL(1)文法。

(2)该文法不含有左递归 1. S -> ABBA 2. A -> a | ε 3. B -> b | ε FIRST集合

FIRST(S) = {a , b , ε } FIRST(A) = {a , ε } FIRST(B) = {b , ε }

FOLLOW集合

FOLLOW(S) = { $ } FOLLOW(A) = {a , b , $} FOLLOW(B) = {a , b , $ }

因为 A -> a | ε ，FIRST(a) ∩ FOLLOW(A) ≠ ∅ 因为 B -> b | ε，FIRST(b) ∩ FOLLOW(B) ≠ ∅

不符合LL(1)文法的要求，不是LL(1)文法